Various methods and techniques have been used to produce more efficient logic networks by reducing path lengths. The publications "Logic Synthesis Through Local Transformation" by J. A. Darringer et al, IBM J. RES. Develop, Vol. 25, No. 4, July, 1981, at pp. 272-280, and "Experiments in Logic Synthesis", Proceedings of IEEE International Conference on Circuits and Computers ICCC 80, Port Chester, N.Y., 1980, pp. 234-237 A, by J. A. Darringer et al, both discuss a system for synthesizing synchronous combinational logic. In the system, simple local transformations are used to incrementally improve the logic network. The system is primarily directed to reducing the size or number of gates of logic networks, but makes some attempts to reduce path lengths.
The publication "Global Flow Analysis in Automatic Logic Design" by L. Trevillyan et al, R.C. 10340 (No. 46137), July 23, 1984, at pp. 1-16, discusses the applications of global flow optimization techniques to automated design of logic. These techniques utilize linear time algorithms which extend the scope of local optimizations to the entire logic network design. The global flow analysis transforms have options which allow them to decrease path lengths by pushing signals forward in the logic network. The method steps employed in the above cited references are set forth in detail in their respective publications, and are different from the method of the present invention. For example, the logic levels in a sample design having approximately 40 gate levels could not be reduced to below 24 levels of NAND gates using the techniques of the above references. Using the method of the present invention, the network was reduced to 10 levels, with only a 3.33% increase in gates, a 3.14% increase in signals, and a 10.8% increase in connections. Moreover, using the method of the invention, the sample design could have been reduced to three levels.
U.S. Pat. No. 4,263,651 discloses a method of determining critical paths within a logic block circuit having a number of logic blocks interconnected by nets which carry logic signals between the logic blocks. The method includes levelizing the logic blocks and determining the long and short path delays so that the circuit can be redesigned. However, this method does not provide correction, and criticality can be determined only at a register input or network output, not at blocks internal to the logic, since only forward levelization is disclosed.
U.S. Pat. Nos. 4,541,067 and 4,566,064 disclose a method of generating combinational logic networks from PASS transistors for increasing the packing density of the resulting logic networks. However, this method begins with the formation of a truth table which represents the function to be implemented, and therefore does not preserve any structural information from a pre-existing logic network.
U.S. Pat. No. 4,377,849 disclose a multipass process for automatically generating complex circuit designs. In the process, logic cells are broken down into basic components of the logic technology add are assembled into prime cells or macros to complete the circuit design.
U.S. Pat. No. 4,386,403 discloses a system for analyzing complex circuits. In the system, a macromodel of repetitive circuitry is utilized. The system also includes means for determining when a macromodel is "latent" or "quiescent", thereby saving time during the analysis of the circuit when a macromodel is latent.
U.S. Pat. No. 3,622,762 discloses a method of improving circuit operation by changing design variables. The method includes an optimizer routine for receiving an objective function and the function's first derivative. In the optimizer routine, original element values are adjusted to improve a numerical representation of the objective function.
U.S. Pat. No. 3,093,751 discloses an "exclusive or"circuit for providing a desired logical result in response to a set of binary inputs.
U.S. Defensive Publication No. T940,020 discloses a method for automatically generating a topology for a logic circuit which will be embodied in a semiconductor wafer. In the method, fixed data, which represent the electrical and topological qualities of each logical element in the logic circuit, are inputted to a computer in the form of an ordered grid array layout. A program generates, for each logical element in the grid array, coordinate data which translate the coordinates into a topological pattern descriptive of the logic circuit.
U.S. Defensive Publication No. T940,013 discloses an automated process for analyzing electrical networks. The process solves a set of node and parameter equations. An "adjoint" equation is solved by weighting each of the "performances", and a sensitivity vector is used to converge on an optimized solution.
U.S Defensive Publication No. T938,005 discloses a process for making LSI chips. The process includes a "design automation" system containing predesigned circuits. The system generates a graphical description of a circuit. The generated description is then merged with a topology from a library to form a complete chip description.
In addition, there are various methods for mapping a logic network. U.S. Defensive Publication Nos. T943,001, T944,001 and T944,008 are cited as examples of such logic mapping methods.
Although the above and various other methods and systems have been used to reduce the path lengths of logic networks, these prior art methods and systems usually require drastic restructuring of the original logic network. Further, these previous methods and systems can reduce gate levels only by a limited amount, or completely compress the logic network into a sum of products form.